Maximum Non-Adjacent Sum
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
A community garden has a single row of plots. Every plot has a yield, a positive number telling you how much you harvest from it this season.
Two plots next to each other share one fence, and that fence can only take being disturbed once a season. So you can never harvest two plots that sit right beside each other. Every other plot is fair game.
Given the yield of every plot in order, return the largest total yield you can harvest this season.
Input: nums = [5, 1, 1, 5]
Output: 10
Harvest plot 0 and plot 3. Their fences never touch, and 5 + 5 = 10 beats any other combination.
Input: nums = [4, 1, 1, 4, 2, 1]
Output: 9
Harvest plot 0, plot 3, and plot 5. None of them are neighbors, and 4 + 4 + 1 = 9.
Input: nums = [3, 7]
Output: 7
With only two plots and a shared fence between them, you can only harvest one. Take the bigger yield.
You might also hear this problem called “House Robber.”
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.